Search results for "K-ary tree"

showing 2 items of 2 documents

On the low-dimensional Steiner minimum tree problem in Hamming metric

2013

While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2-2d approximation on the Steiner minimum tree for d>=2. Using this result, we analyse the so-called k-LCA and A"k approximation algorithms and show improved approximation guarantees for low dimensions.

Discrete mathematicsK-ary treeGeneral Computer ScienceMinimum spanning treek-minimum spanning treeSteiner tree problemTheoretical Computer ScienceCombinatoricssymbols.namesakeHamming graphsymbolsMetric treeGomory–Hu treeMathematicsVantage-point treeTheoretical Computer Science
researchProduct

Tree automata, tree decomposition and hyperedge replacement

2005

Recent results concerning efficient solvability of graph problems on graphs with bounded tree-width and decidability of graph properties for hyperedge-replacement graph grammars are systematised by showing how they can be derived from recognisability of corresponding tree classes by finite tree automata, using only well-known techniques from tree-automata theory.

Discrete mathematicsSPQR treeSpanning treeK-ary treeComputer scienceTree decompositionCombinatoricsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTree structureGomory–Hu treeTree automatonGraph propertyComputer Science::Formal Languages and Automata TheoryMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct